The operation of a plant—in this description and in the attached claims this term means industrial plants, manufacturing or research equipment, various types of vehicles (e.g. aircraft)—is controlled usually by means of complex diagnostic systems able to detect and isolate faulty operation conditions as soon as they happen.
In the last few decades research in the field of model-based diagnostics has developed mainly along two different approaches: the first one (FDI, Fault Detection and Isolation) is based on automatic control theory and statistical decisions, while the second, called DX, is based on artificial intelligence techniques. The basic principle of model-based diagnostics is to compare the nominal or expected behavior of a system, provided by a model of the system, to the actual behavior shown by measurements on the system. An Analytical Redundancy Relation, ARR, also known as residual or parity equation, used in the FDI approach, is a relation among measured parameters of the system. Any unsatisfied ARR would represent a discrepancy between the expected and the actual behavior of the system. The DX approach is based on the concept of conflict, which is a set of assumptions on the modes of some components that is not consistent with the model of the system and the measurements. Recently a unifying framework has shown the equivalence of both approaches. The link between the concepts of ARR and of conflict is that the support of an ARR, i.e., the set of components involved in that ARR, is a possible conflict, i.e., there is a possible scenario of measurements on the system which produces that set as a conflict.
The Analytical Redundancy Relations have an important role not only in system diagnostics, but also in analysis and optimization of the systems of sensors used for diagnostic purposes.
The quality and efficiency of a diagnostic system depends on the availability and relevance of the information that said system can obtain from the system under diagnosis. The quality of the measurements is expressed by the diagnosability degree, i.e., given a set of sensors, by which faults can be discriminated. There is no simple relation between the number of sensors and the diagnosability degree of a system. Just increasing the number of sensors does not necessarily guarantee a higher level of diagnosability, while on the other hand it is desirable to achieve a desired degree of diagnosability at the lowest possible cost.
The structural properties of the plant under control and the potential information carried by each sensor are presented in the set of ARRs. The information from the set of all ARRs can be summarized in a signature matrix.
The problem of sensor optimization can therefore be formulated as a combinatorial problem applied to the signature matrix, or as an integer programming problem involving said matrix.
Analytical Redundancy Relations and Fault Signature Matrix
In the following the concepts of Analytical Redundancy Relations (ARR) and Fault Signature Matrix (FSM) will be introduced and briefly explained. For clarity and simplicity, the case of a single fault of a system will be assumed.
The System Model (SM) is defined to consist of the Behavioral Model (BM) and the Observation Model (OM) The Behavioral Model BM is a component-based description of the system and consists of a set of Primary Relations (PRs). Each component is described by the function that it performs, i.e., by one or more PRs, and its inputs and outputs, such a component-based description also includes the topology of the system. The OM is the set of relations defining the observations that are performed on the system and the sensor models.
FIG. 1 shows an example of a polybox system consisting of three Multipliers (M1, M2, M3) and two adders (A1, A2).
The Behavioral Model BM for this system, representing a component-based description and the topology, is given by a set of PRs and their associated components as:                PR1: x=a c; M1         PR2: y=b d; M2         PR3: z=c e; M3         PR4: f=x+y; A1         PR5: g=y+z; A2         
The set of variables (V) of the system can be decomposed into the set of unknown (unobserved) variables (X) and the set of observed variable (O), i.e., V=X∪O.
A Redundancy Relation (ARR) is a constraint deduced from the system model (SM). ARRs can be derived from SM by eliminating the unknown (unobserved) variables from the PRs. Therefore, an ARR contains only, and hence can be evaluated from, observed variables.
An associated concept is the support of an ARR, that is, the subset of components that are involved in the derivation of the ARR.
For the system of FIG. 1, if the sensors are placed at outputs f and g, and with known inputs a-e, then O={a, b, c, d, e, f, g} and X={x, y, z}.
The resulting ARRs are given in following Table:
TABLE 1ARR, support components, and sensorsfor the polybox example in FIG. 1SupportARRsComponentsSensorsARR1: f = ac + bdM1, M2, A1fARR2: g = bd + ceM2, M3, A2gARR3: f − g = ac − ceM1, M3, A2, A1f, g
ARRs are used to check the consistency of the observations with respect to SM. That is, the ARRs are satisfied if the observed system behavior satisfies the model constraint. Under single-fault exoneration assumption, if a component of an ARR support is faulty, then that ARR is not satisfied. In fact, coupled with the concept of support set, this forms the foundation of model-based diagnosis approach in the FDI community
Let us consider the Fault Signature Matrix (FSM), resulting from the derivation of ARRs. The FSM is defined as a binary (0-1) matrix whose rows are ARRs and columns are faults (components). An element FSij of this matrix is assigned 1 if component Ci is part of support of ARRj, otherwise FSij=0. The i-th column corresponding to component Ci is defined as the fault signature vector of Ci and it is denoted as FSi=[FSi1, . . . , FSin]t.
For the polybox system of FIG. 1, the FSM can be derived from Table 1 and is given in Table 2.
TABLE 2Fault Signature Matrix for Polybox System of FIG. 1A1A2M1M2M3ARR110110ARR201011ARR311101
The model-base diagnosis approach in FDI is based on evaluation of ARRs given a set of system observations.
If an ARRi is satisfied based on the observation, then ARRi=0, otherwise ARRi=1. The ARRs are instantiated with the observed values providing an observed signature. The signature of i-th observation is defined as a binary vector OSi=[OSi1, . . . , OSin]t, where OSij=0 if ARRj is satisfied by the observations, and OSij=1 otherwise.
Table 3 shows the diagnosis of the polybox system of FIG. 1 based on different observation signatures.
TABLE 3Diagnosis of polybox system of FIG. 1 usingARRs for different Observation SignaturesObsARR100111ARR201011ARR301101Fault DiagnosisnoneA2; M3A1; M1M2none
The diagnosis is then based on the faults accounted for in the fault signature matrix. That is, an observed signature OSi=[OSi1, . . . , OSin]t is consistent with a fault signature FSi=[FSi1, . . . , FSin]t if FSij=OSij for all j.
As an example, for the polybox system of FIG. 1, the observation signature [0,1,1]t is equivalent to the fault signature of components A2 and M3. Note that this indicates that, due to the system sensors, the faults of A2 and M3 cannot be discriminated, as is the case for A1 and M1.
The criteria of fault detection and isolation (faults discrimination) can be described in terms of FSM.
All faults can be detected (full detection) if there is no all zero column (i.e., no zero fault signature vector) in FSM. That is, for a given faulty component Ci at least one ARR is affected. The isolation is assured by requiring that no two columns of FSM be identical since it implies that the two fault signature vectors are identical and hence cannot be distinguished.
The above discussion allows a straightforward description of the sensors analysis approach. Given an SM and a set of deployed sensors, derive the corresponding set of ARRs and form the corresponding FSM. The analysis of the resulting FSM can reveal the degree of detection, i.e. the number of all zero columns, which implies faulty components with zero fault signature vectors, and the ambiguity sets, i.e., the number and groups of faulty components with identical signature vectors, which implies the sets of components whose fault cannot be distinguished.
Considering what written above a preliminary statement of sensor optimization problem can be also given as follows. Starting with a SM, assign a hypothetical sensor to any point in the system which can be, physically and practically, measured (i.e., a sensor can be deployed at that point). Assign a cost function to any hypothetical sensor. Then derive the set of ARRs for this set of hypothetical sensors and form the corresponding FSM, called the Hypothetical Fault Signature Matrix (HFSM).
The optimization process can now be described as follows. Eliminate the subset of sensors with maximum cost (i.e., retain the subset of sensors with the minimum cost) while achieving maximum detection and isolation. Mathematically, this process is performed as follows: For a subset of sensors to be deleted, eliminate the ARRs which are affected by these sensors. Check the resulting FSM for detection and isolation, i.e., for no zero columns and no two identical columns.
It can be seen that this process does not represents a rigorous formulation of the optimization problem. And, in fact, current approaches to sensor optimization, based on the concept of FSM, are based on exhaustive searches which can be only applied to small systems.
It can be concluded that a key step and challenge in both sensor optimization and analysis is the derivation of ARRs to form the FSM.
Complexity of Derivation of Analytical Redundant Relations
A key problem in the application of ARRs is the efficient derivation of the complete set of ARRs. In the following, we discuss some key issues regarding the complexity of the derivation of ARRs.
Possible Number of ARRs
The first issue is actually the possible number of Analytical Redundant Relations. Consider a system described by n Primary Relations (usually this means that the system has n components, but in general this could imply that the system has at most n components) and m sensors (observations) where, for most practical cases, n>m.
If one considers the ARRs only as functions of all possible combinations of observations, then one would conclude that the total number of ARRs would be of the order of O(2m). On the other hand, if one considers that ARRs are obtained from combination of PRs, through elimination of unknown variables, this would then imply an upper bound of O(2n) for the number of ARRs.
The key point, which the inventors believe has not received sufficient attention in the technical note, is that ARRs can involve all possible combinations of PRs and observations.
In fact, a same set of PRs can lead to different ARRs, that is, ARRs with same set of support components but with different set of observations.
One can also consider cases wherein a same set of observations could lead to different ARRs which differ in their support components.
Taking this view, it can then be concluded that the upper bound on total number of ARRs is in fact of the order of O(2n+m). Note that for any practical system of interest the number of ARRs would be finite due to the system's structural constraints. In fact, an infinite number of ARRs implies that the system is not diagnosable!
Completeness of Set of ARRs and Redundant ARRs
A key fundamental issue in application of ARRs for both diagnosis and sensor placement is the completeness of the set of ARRs.
More precisely, it seems that the issue of minimal complete set of ARRs has not received enough attention.
In the literature the two concepts of d-completeness (completeness for detection of faults) and i-completeness (completeness for isolation of faults) have been discussed. However, these two concepts can be applied for analysis of applicability of a given set of ARRs for diagnosis. And, it seems that there is no discussion of the derivation of complete set of ARRs in the literature. It is quite obvious that completeness is a fundamental issue in both diagnosis and sensor placement since maximum available information provided by ARRs is needed.
It is also obvious that any application of an incomplete set of ARRs for both diagnosis and sensor placement might lead to wrong and/or suboptimal results.
Let's consider the definition of ARRs: “an ARR is a constraint deduced from the system model which contains only observed variables, and which can therefore be evaluated from any observer”. Following this definition, then any trivial combination of any existing two ARRs can be then consider as a new ARR. Therefore, such a definition can lead to derivation of redundant ARRs.
In order to assure the completeness, we should consider all possible combinations of PRs in an exhaustive and complete fashion. In fact, if the focus of a method is only on searching the common variables and their elimination, as is the case for the known algorithm, then this would lead to an incomplete set of ARRs and, depending on the ordering in variable elimination, to ARRs sets with variable size.
We consider a set of ARRs as a complete set if it can be shown that any new ARR is just a trivial combination of existing ARRs.
We define a redundant ARR as one that can be obtained by trivial combination of existing ARRs, e.g., addition of two existing ARRs without eliminating any unknown variables.
An interesting example is the system of FIG. 1.
While ARR3 of Table 1 seems to be a simple subtraction of ARR1 and ARR2, indeed it has been obtained through elimination of unknown variables at several steps. However, a simple addition of ARR1 and ARR2 will lead to a redundant ARR which does not provide any information for diagnosis.
The problem with redundant ARRs is that they can significantly increase the complexity of the derivation of ARRs, even leading to an exponential complexity.
To see this, consider a system with L ARRs. If any trivial combination of any existing ARRs is consider as a new ARR, then this would lead possibly to a total number of O(2L) ARRs and hence the exponential complexity in the derivation.
The key point is that, a given algorithm might also derive redundant ARRs, even though it avoids trivial combination of existing ARRs, thus resulting in an exponential complexity in the derivation.
Consider a basic definition for derivation of ARRs as “ARRs can be obtained from the system model by eliminating the unknown variables”. However, eliminating a common unknown variable between two ARRs might lead to a redundant ARR. To see this, note that as we stated before, we also define an ARR based on the set of PRs used for its derivation. If two ARRs have a common unknown variable but also a common PR in their derivation, then the elimination of the common variable would lead to an ARR which is a trivial combination of previous ARRs, i.e. a redundant ARR.
Complexity of Derivation of ARRs
An ARR is obtained as a result of combination of a set of Primary Relations through elimination of unknown variables. Such a process is associative and hence can be performed in any order. Consider an ARRi resulting from combination of k Primary Relations. Neglecting the first combination of two PRs in its derivation, and considering all possible ordering in the derivation, it then follows that the same ARRi might be obtained, possibly, in at most k!/2 ways. In fact, if a given algorithm performs an exhaustive search for finding common unknown variables and derive new ARRs by eliminating the common variable, then the same ARR might be derived many times, potentially in a factorial time in the number of PRs, which might lead to an algorithm with time complexity factorial in the number of primary relations. Indeed, it seems that the exponential complexity of known algorithm, which is based on finding and eliminating common variables, is due to this fact. Given the associative nature of derivation of the ARRs, it seems that the repetition in the derivation of an ARR cannot be avoided.
Currently, although the concept of ARRs provides a powerful framework for sensors optimization and system diagnosability, the inventors believe that the development of efficient systematic approaches for their generation has not received sufficient attention. The current processes for the generation of analytical redundancy relations are in fact dependent on the system they describe, and the derivation of a complete set of ARR depends essentially on the experience and knowledge of an expert programmer to manipulate analytical equations, and can not be extended easily to a large number of systems or plants of interest.